package p400;

import java.util.Arrays;

/**
 * @author pengjz <br>
 * @version 1.0 <br>
 * @description Leetcode_475 <br>
 * @date 2021/12/20 16:05 <br>
 */
public class Leetcode_475 {

    public int findRadius(int[] houses, int[] heaters) {
        // 对于所有房屋。找离自己最近的取暖器，最后返回最大的
        // 先排序
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int max = 0;
        for (int house : houses) {
            int nearestHeater = binarySearch(heaters, house) - house;
            if (nearestHeater > max) {
                max = nearestHeater;
            }
        }
        return max;
    }

    public int binarySearch(int[] a, int key) {
        int low = 0, high = a.length - 1;
        if (a[low] > key) {
            return a[low];
        }
        if (a[high] < key) {
            return a[high];
        }
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];
            if (midVal < key) {
                if (mid != high - 1 && a[mid + 1] > key) {
                    return Math.abs(key - midVal) > Math.abs(key - a[mid + 1]) ? a[mid + 1] : midVal;
                }
                low = mid + 1;
            } else if (midVal > key) {
                if (mid != low + 1 && a[mid - 1] < key) {
                    return Math.abs(key - midVal) > Math.abs(key - a[mid - 1]) ? a[mid - 1] : midVal;
                }
                high = mid - 1;
            } else {
                return midVal;
            }
        }
        return a[low];
    }


    public static void main(String[] args) {
        final Leetcode_475 leetcode_475 = new Leetcode_475();
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, -2));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 1));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 2));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 4));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 6));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 8));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 9));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 10));
        System.out.println(leetcode_475.binarySearch(new int[]{1, 6, 7, 10}, 11));

    }

}
